#include <iostream>
using namespace std;

struct matrixTerm
{ // 三元组结构体定义
    int row, col, value;
    matrixTerm &operator=(matrixTerm &x)
    { // 运算符重载 ，赋值*this = x
        row = x.row;
        col = x.col;
        value = x.value;
        return *this;
    }
};
const int maxsize = 199999; // 新matrixTerm创建最大容量设定

class sparseMatrix // 稀疏矩阵类定义
{
private:
    int Rows;            // 行
    int Cols;            // 列
    int Terms;           // 非零元素个数
    matrixTerm *element; // 用来存非零元素的数组
    int maxSize;         // 数组最大容量
public:
    sparseMatrix(int n, int m) // 构造函数
    {
        element = new matrixTerm[maxsize];
        Rows = n;
        Cols = m;
        Terms = 0;
    }
    ~sparseMatrix() { delete[] element; } // 析构函数
    sparseMatrix &operator=(sparseMatrix &a)
    { // 运算符重载 ，赋值*this = a
        Rows = a.Rows;
        Cols = a.Cols;
        Terms = a.Terms;
        maxSize = a.maxSize;
        for (int i = 0; i < Terms; i++)
            element[i] = a.element[i];
        return *this;
    }
    void inputAelement(int x, int y, int v); // 辅助函数——非0值输入
    void initial(int n, int m);              // 重置1
    int multiply(sparseMatrix &a);           // 乘法2
    int add(sparseMatrix &a);                // 加法3
    void output();                           // 输出4
    void transpose();                        // 转置5
};

// 辅助函数——非0值输入，更新三元组
void sparseMatrix::inputAelement(int x, int y, int v)
{
    matrixTerm New;
    New.row = x;   // 行序号
    New.col = y;   // 列序号
    New.value = v; // 非零元素值
    element[Terms] = New;
    Terms++;
}

// 重置1
void sparseMatrix::initial(int n, int m)
{
    Rows = n;
    Cols = m;
    Terms = 0;
    for (int i = 1; i <= Rows; i++)
    { // 按行优先顺序输入矩阵的各个元素
        for (int j = 1; j <= Cols; j++)
        {
            int b;
            cin >> b;
            if (b != 0)
            {
                element[Terms].row = i;
                element[Terms].col = j;
                element[Terms].value = b;
                Terms++;
            }
        }
    }
}

// 乘法2
int sparseMatrix::multiply(sparseMatrix &Q)
{
    // 有效性检验
    if (Cols != Q.Rows)
    { // 按矩阵乘法C[m,n]= P[m,k] ×Q[k,n]，需要有Cols=Q.Rows
        *this = Q;
        return -1;
    }
    else
    {
        // 取乘数P的行和乘数Q的列构建结果sparseMatrix
        sparseMatrix C(Rows, Q.Cols);
        int num[10000];    // 每行非零元素的个数
        int Index[10000];  // 每行第一个非零元素对应的索引
        int Answer[10000]; // 存放乘法结果

        // 每行计数清零
        for (int i = 1; i <= Q.Rows; i++)
            num[i] = 0;
        // 计数得第i行对应非零元素个数
        for (int i = 0; i < Q.Terms; i++)
        {
            if (Q.element[i].value != 0)
                num[Q.element[i].row]++;
        }
        // 第i行第一个非零元素索引
        Index[1] = 0;
        for (int i = 2; i <= Q.Terms; i++)
            Index[i] = Index[i - 1] + num[i - 1];

        // 开始乘法计算C[m,n]= P[m,k] ×Q[k,n]
        int p = 0;
        for (int i = 1; i <= Rows && p < Terms; i++)
        {
            // 赋初值0
            for (int j = 1; j <= Q.Cols; j++)
                Answer[j] = 0;
            while (p < Terms && element[p].row == i) // 循环条件为仍有非零元素且第i行有非零元素
            {
                int t = element[p].col;
                if (num[t] != 0) // P有非0元素的行对应的Q里的列任有非0元素
                {                // 如果都是0了，乘法所得也不会是非0，这个判断起简化作用
                    for (int q = Index[t]; q < Index[t] + num[t]; q++)
                        // 计算对应i行每列的乘积
                        Answer[Q.element[q].col] += element[p].value * Q.element[q].value;
                }
                // 继续下一个非零元素
                p++;
            }
            for (int k = 1; k <= Q.Cols; k++)
            { // 结果中的非0元素导出三元组
                if (Answer[k] != 0)
                {
                    C.element[C.Terms].value = Answer[k];
                    C.element[C.Terms].row = i;
                    C.element[C.Terms].col = k;
                    C.Terms++;
                }
            }
        }
        *this = C;
        return 0;
    }
}

// 加法3
int sparseMatrix::add(sparseMatrix &Q)
{
    if (Q.Cols != Cols || Q.Rows != Rows) // 根据矩阵加法规则，行列不等不符合
    {
        *this = Q;
        return -1;
    }
    else
    {
        sparseMatrix C(Rows, Cols); // 设置结果矩阵的特征
        int it = 0, ib = 0;
        while (it != Terms && ib != Q.Terms) // 遍历，把相关的项相加
        {                                    // 行主索引加上每一项的列数
            int tIndex = (element[it]).row * Cols + (element[it]).col;
            int bIndex = (Q.element[ib]).row * Cols + (Q.element[ib]).col;
            if (tIndex < bIndex)
            { // Q项在后
                C.element[C.Terms].col = element[it].col;
                C.element[C.Terms].row = element[it].row;
                C.element[C.Terms].value = element[it].value;
                it++;
                C.Terms++;
            }
            else if (tIndex == bIndex)
            { // 两项在同一个位置
                if ((element[it]).value + (Q.element[ib]).value != 0)
                { // 仅当相加后不为0时加入c
                    C.element[C.Terms].col = (element[it]).col;
                    C.element[C.Terms].row = (element[it]).row;
                    C.element[C.Terms].value = (element[it]).value + (Q.element[ib]).value;
                    C.Terms++;
                }
                it++;
                ib++;
            }
            else
            {
                C.element[C.Terms].col = Q.element[ib].col;
                C.element[C.Terms].row = Q.element[ib].row;
                C.element[C.Terms].value = Q.element[ib].value;
                ib++;
                C.Terms++;
            }
        }
        // 复制剩余项
        for (; it != Terms; it++)
        {
            C.element[C.Terms].col = element[it].col;
            C.element[C.Terms].row = element[it].row;
            C.element[C.Terms].value = element[it].value;
            C.Terms++;
        }
        for (; ib != Q.Terms; ib++)
        {
            C.element[C.Terms].col = Q.element[ib].col;
            C.element[C.Terms].row = Q.element[ib].row;
            C.element[C.Terms].value = Q.element[ib].value;
            C.Terms++;
        }
        *this = C;
        return 0;
    }
}

// 输出4
void sparseMatrix::output()
{
    int i, j, k = 0;
    cout << Rows << " " << Cols << endl;
    for (i = 0; i < Rows; i++) // 遍历输出
    {
        for (j = 0; j < Cols; j++)
        {
            if (k < Terms && element[k].row == i + 1 && element[k].col == j + 1)
            {
                cout << element[k].value << " ";
                k++;
            }
            else
                cout << 0 << " ";
        }
        cout << endl;
    }
}

// 转置5
void sparseMatrix::transpose()
{
    // 设置转置矩阵特征
    sparseMatrix b(Cols, Rows);
    b.Terms = Terms;
    b.Cols = Rows;
    b.Rows = Cols;
    // 初始化
    int *colSize = new int[Cols + 1]; // 矩阵第i列的非零元素个数
    int *rowNext = new int[Cols + 1]; // 矩阵第i列第一个非零元素索引

    // 计算待转置矩阵中每一列非0元素的个数
    for (int i = 1; i <= Cols; i++)
        colSize[i] = 0;
    for (int i = 0; i < Terms; i++)
        colSize[element[i].col]++;
    // 确定矩阵第i列第1个非0元素的对应索引
    rowNext[1] = 0;
    for (int i = 2; i <= Cols; i++)
        rowNext[i] = rowNext[i - 1] + colSize[i - 1];
    // 上述几步和乘法中同理，提高程序针对稀疏矩阵运算效率

    // 实施从*this到b的转置复制
    for (int i = 0; i < Terms; i++)
    {
        int j = rowNext[element[i].col];
        // 行列转置
        b.element[j].row = element[i].col;
        b.element[j].col = element[i].row;
        b.element[j].value = element[i].value;
        rowNext[element[i].col] = rowNext[element[i].col] + 1;
        // 对应列rowNext索引+1，以防同一列有多个非零元素 (防撞）
    }
    *this = b;
}

int main()
{
    sparseMatrix P(0, 0);
    int w;           // 操作个数
    int panduan = 0; // 各种不合法输出工具变量
    int n;           // 矩阵行数
    int m;           // 矩阵列数
    int t;           // 矩阵非0元素个数
    int trans;       // 操作编码
    cin >> w;
    for (int i = 0; i < w; i++)
    {
        cin >> trans;
        if (trans == 1)
        { // 重置矩阵
            cin >> n >> m;
            P.initial(n, m);
        }
        else if (trans == 2)
        { // 矩阵乘法
            cin >> n >> m;
            cin >> t;
            sparseMatrix Q1(n, m);
            for (int i = 0; i < t; i++)
            {
                // Q矩阵非零元素的行、列序号及非0元素值
                int x, y, v;
                cin >> x >> y >> v;
                Q1.inputAelement(x, y, v);
            }
            panduan = P.multiply(Q1);
            if (panduan == -1)
                cout << panduan << endl;
        }
        else if (trans == 3)
        { // 矩阵加法
            cin >> n >> m;
            cin >> t;
            sparseMatrix Q2(n, m);
            for (int i = 0; i < t; i++)
            {
                int x, y, v;
                cin >> x >> y >> v;
                Q2.inputAelement(x, y, v);
            }
            panduan = P.add(Q2);
            if (panduan == -1)
                cout << panduan << endl;
        }
        else if (trans == 4)
            // 输出操作
            P.output();
        else
            // 转置
            P.transpose();
    }
    return 0;
}